{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Pacific Atlantic Water Flow"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: pacificAtlantic"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #太平洋大西洋水流问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个 <code>m × n</code> 的矩形岛屿，与 <strong>太平洋</strong> 和 <strong>大西洋</strong> 相邻。&nbsp;<strong>“太平洋”&nbsp;</strong>处于大陆的左边界和上边界，而 <strong>“大西洋”</strong> 处于大陆的右边界和下边界。</p>\n",
    "\n",
    "<p>这个岛被分割成一个由若干方形单元格组成的网格。给定一个 <code>m x n</code> 的整数矩阵&nbsp;<code>heights</code>&nbsp;，&nbsp;<code>heights[r][c]</code>&nbsp;表示坐标 <code>(r, c)</code> 上单元格 <strong>高于海平面的高度</strong> 。</p>\n",
    "\n",
    "<p>岛上雨水较多，如果相邻单元格的高度 <strong>小于或等于</strong> 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。</p>\n",
    "\n",
    "<p>返回网格坐标 <code>result</code>&nbsp;的 <strong>2D 列表</strong> ，其中&nbsp;<code>result[i] = [r<sub>i</sub>, c<sub>i</sub>]</code>&nbsp;表示雨水从单元格 <code>(ri, ci)</code> 流动 <strong>既可流向太平洋也可流向大西洋</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/06/08/waterflow-grid.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]\n",
    "<strong>输出:</strong> [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> heights = [[2,1],[1,2]]\n",
    "<strong>输出:</strong> [[0,0],[0,1],[1,0],[1,1]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == heights.length</code></li>\n",
    "\t<li><code>n == heights[r].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 200</code></li>\n",
    "\t<li><code>0 &lt;= heights[r][c] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [pacific-atlantic-water-flow](https://leetcode.cn/problems/pacific-atlantic-water-flow/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [pacific-atlantic-water-flow](https://leetcode.cn/problems/pacific-atlantic-water-flow/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]', '[[1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        if not heights:\n",
    "            return []\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        p_visited, a_visited = set(), set()\n",
    "\n",
    "        def dfs(i,j,visited):\n",
    "            q=[(i,j)]\n",
    "            while q:\n",
    "                x,y = q.pop()\n",
    "                visited.add((x,y))\n",
    "                for dx, dy in [(0,1),(0,-1),(1,0),(-1,0)]:\n",
    "                    if 0<= x+dx<m and 0<=y+dy<n and (x+dx,y+dy) not in visited and heights[x+dx][y+dy]>=heights[x][y]:\n",
    "                        q.append((x+dx, y+dy))\n",
    "\n",
    "        for row in range(m):\n",
    "            dfs(row,0,p_visited)\n",
    "            dfs(row,n-1,a_visited)\n",
    "\n",
    "        for col in range(n):\n",
    "            dfs(0,col,p_visited)\n",
    "            dfs(m-1,col,a_visited)\n",
    "        return list(a_visited & p_visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        # 方法二：广度优先搜索\n",
    "        # time complexity: O(mn)\n",
    "        if not matrix or not matrix[0]:\n",
    "            return []\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        Pacific = [[False]*n for _ in range(m)]\n",
    "        Atlantic = [[False]*n for _ in range(m)]\n",
    "        queue = deque([])\n",
    "        for y in range(n):\n",
    "            queue.append((0,y))\n",
    "        for x in range(1,m):\n",
    "            queue.append((x,0))\n",
    "        while queue:\n",
    "            length = len(queue)\n",
    "            for _ in range(length):\n",
    "                x, y = queue.popleft()\n",
    "                Pacific[x][y] = True\n",
    "                for dx, dy in [[-1,0],[1,0],[0,1],[0,-1]]:\n",
    "                    nx, ny = x+dx, y+dy\n",
    "                    if 0<=nx<m and 0<=ny<n and not Pacific[nx][ny] and matrix[x][y] <= matrix[nx][ny]:\n",
    "                        queue.append((nx, ny))\n",
    "        queue = deque([])\n",
    "        for y in range(n):\n",
    "            queue.append((m-1, y))\n",
    "        for x in range(m-1):\n",
    "            queue.append((x, n-1))\n",
    "        while queue:\n",
    "            length = len(queue)\n",
    "            for _ in range(length):\n",
    "                x, y = queue.popleft()\n",
    "                Atlantic[x][y] = True\n",
    "                for dx, dy in [[-1,0],[1,0],[0,1],[0,-1]]:\n",
    "                    nx, ny = x+dx, y+dy\n",
    "                    if 0<=nx<m and 0<=ny<n and not Atlantic[nx][ny] and matrix[x][y] <= matrix[nx][ny]:\n",
    "                        queue.append((nx, ny))\n",
    "        ans = []\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if Pacific[x][y] and Atlantic[x][y]:\n",
    "                    ans.append([x,y])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "\n",
    "        if not matrix:\n",
    "            return []\n",
    "        step = [[-1, 0], [1, 0], [0, -1], [0, 1]]  # 上下左右四个方向\n",
    "        result_list = []\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        # DFS+记忆存储\n",
    "        p_flag = [[False]*n for _ in range(m)]  # 有哪些格子能够流入太平洋\n",
    "        a_flag = [[False]*n for _ in range(m)]  # 有哪些格子能够流入大西洋\n",
    "\n",
    "        # 从四条边开始\n",
    "        for row_idx in range(m):\n",
    "            # 左边的列\n",
    "            self.dfs_search(row_idx, 0, p_flag, step, m, n, matrix)\n",
    "            # 右边的列\n",
    "            self.dfs_search(row_idx, n-1, a_flag, step, m, n, matrix)\n",
    "\n",
    "        for col_idx in range(n):\n",
    "            # 上边的行\n",
    "            self.dfs_search(0, col_idx, p_flag, step, m, n, matrix)\n",
    "            # 下边的行\n",
    "            self.dfs_search(m-1, col_idx, a_flag, step, m, n, matrix)\n",
    "\n",
    "        for row_idx in range(m):\n",
    "            for col_idx in range(n):\n",
    "                if p_flag[row_idx][col_idx] and a_flag[row_idx][col_idx]:\n",
    "                    result_list.append([row_idx, col_idx])\n",
    "        return result_list\n",
    "\n",
    "    def dfs_search(self, row_num, col_num, visited_matrix, step, m, n, matrix):\n",
    "        # 能够进入就表明当前格子可以被访问\n",
    "        visited_matrix[row_num][col_num] = True\n",
    "        for x, y in step:\n",
    "            # 遍历上下左右，让水流逆流而上\n",
    "            new_row = row_num+x\n",
    "            new_col = col_num+y\n",
    "            # 找到可以顺流而上的条件，在格子内，周边格子高度比当前高，且周边格子还没走过\n",
    "            if 0 <= new_row < m and 0 <= new_col < n and matrix[new_row][new_col] >= matrix[row_num][col_num] \\\n",
    "                    and visited_matrix[new_row][new_col] is False:\n",
    "                self.dfs_search(new_row, new_col, visited_matrix, step, m, n, matrix)\n",
    "\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if not matrix:\n",
    "            return []\n",
    "\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        Pacific = [[False for i in range(n)] for j in range(m)]\n",
    "        Atlantic = [[False for i in range(n)] for j in range(m)]\n",
    "\n",
    "        Pacific_border = [(0, col) for col in range(n)] + [(row, 0) for row in range(m)]\n",
    "        Atlantic_border = [(m-1, col) for col in range(n)] + [(row, n-1) for row in range(m)]\n",
    "\n",
    "        for x, y in Pacific_border:\n",
    "            stack = [[x, y]]\n",
    "            while stack:\n",
    "                x, y = stack.pop()\n",
    "                Pacific[x][y] = True\n",
    "                if x - 1 >= 0 and matrix[x - 1][y] >= matrix[x][y] and not Pacific[x-1][y]:\n",
    "                    stack.append([x - 1, y])\n",
    "                if x + 1 < m and matrix[x + 1][y] >= matrix[x][y] and not Pacific[x+1][y]:\n",
    "                    stack.append([x + 1, y])\n",
    "                if y - 1 >= 0 and matrix[x][y - 1] >= matrix[x][y] and not Pacific[x][y-1]:\n",
    "                    stack.append([x, y - 1])\n",
    "                if y + 1 < n and matrix[x][y + 1] >= matrix[x][y] and not Pacific[x][y+1]:\n",
    "                    stack.append([x, y + 1])\n",
    "\n",
    "        for x, y in Atlantic_border:\n",
    "            stack = [[x, y]]\n",
    "            while stack:\n",
    "                [x, y] = stack.pop()\n",
    "                Atlantic[x][y] = True\n",
    "                if x - 1 >= 0 and matrix[x - 1][y] >= matrix[x][y] and not Atlantic[x-1][y]:\n",
    "                    stack.append([x - 1, y])\n",
    "                if x + 1 < m and matrix[x + 1][y] >= matrix[x][y] and not Atlantic[x+1][y]:\n",
    "                    stack.append([x + 1, y])\n",
    "                if y - 1 >= 0 and matrix[x][y - 1] >= matrix[x][y] and not Atlantic[x][y-1]:\n",
    "                    stack.append([x, y - 1])\n",
    "                if y + 1 < n and matrix[x][y + 1] >= matrix[x][y] and not Atlantic[x][y+1]:\n",
    "                    stack.append([x, y + 1])\n",
    "\n",
    "        points = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if Pacific[i][j] and Atlantic[i][j]:\n",
    "                    points.append([i, j])\n",
    "        return points"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:        \n",
    "    def traverse(self, matrix, i, j):\n",
    "        if self.visit[i][j]: return  # 已访问 跳过\n",
    "        self.visit[i][j] = True  # 标记为已访问\n",
    "        ls = [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]  # 当前结点打开后获得的子结点\n",
    "        for tp in ls:\n",
    "            i2, j2 = tp\n",
    "            if (\n",
    "                0 <= i2 < self.rn and 0 <= j2 < self.cn and \\\n",
    "                matrix[i2][j2] >= matrix[i][j] and not self.visit[i2][j2]\n",
    "            ):\n",
    "                self.traverse(matrix, i2, j2)\n",
    "    \n",
    "    def pacific(self, matrix):\n",
    "        i = 0\n",
    "        for j in range(self.cn):\n",
    "            self.traverse(matrix, i, j)\n",
    "        j = 0\n",
    "        for i in range(1, self.rn):\n",
    "            self.traverse(matrix, i, j)\n",
    "        return self.visit\n",
    "\n",
    "    def atlantic(self, matrix):\n",
    "        i = self.rn - 1\n",
    "        for j in range(self.cn):\n",
    "            self.traverse(matrix, i, j)\n",
    "        j = self.cn - 1\n",
    "        for i in range(self.rn-2, -1, -1):\n",
    "            self.traverse(matrix, i, j)\n",
    "        return self.visit\n",
    "\n",
    "    def pacificAtlantic(self, matrix: 'List[List[int]]') -> 'List[List[int]]':\n",
    "        self.rn = len(matrix)\n",
    "        if self.rn != 0:self.cn = len(matrix[0])\n",
    "        else: return []\n",
    "        self.visit = [[False for _ in range(self.cn)] for _ in range(self.rn)]\n",
    "        p = self.pacific(matrix)\n",
    "        self.visit = [[False for _ in range(self.cn)] for _ in range(self.rn)]\n",
    "        a = self.atlantic(matrix)\n",
    "        ls = [[i, j] for i in range(self.rn) for j in range(self.cn) if p[i][j] and a[i][j]]\n",
    "        return ls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if not matrix: \n",
    "            return []\n",
    "        step = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        res = []\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "        q_flag = [[False] * col for _ in range(row)]\n",
    "        a_flag = [[False] * col for _ in range(row)]\n",
    "\n",
    "        def dfs(i, j, visited):\n",
    "            visited[i][j] = True\n",
    "            for x, y in step:\n",
    "                tmp_i, tmp_j = i + x, j + y\n",
    "                if tmp_i < 0 or tmp_j < 0 or tmp_i >= row or tmp_j >= col or matrix[tmp_i][tmp_j] < matrix[i][\n",
    "                    j] or visited[tmp_i][tmp_j]:\n",
    "                    continue\n",
    "                dfs(tmp_i, tmp_j, visited)\n",
    "\n",
    "        for m in range(row):\n",
    "            dfs(m, 0, q_flag)\n",
    "            dfs(m, col - 1, a_flag)\n",
    "        for n in range(col):\n",
    "            dfs(0, n, q_flag)\n",
    "            dfs(row - 1, n, a_flag)\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if q_flag[i][j] and a_flag[i][j]:\n",
    "                    res.append([i, j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=417 lang=python3\n",
    "#\n",
    "# [417] 太平洋大西洋水流问题\n",
    "#\n",
    "# https://leetcode-cn.com/problems/pacific-atlantic-water-flow/description/\n",
    "#\n",
    "# algorithms\n",
    "# Medium (37.15%)\n",
    "# Total Accepted:    753\n",
    "# Total Submissions: 2K\n",
    "# Testcase Example:  '[[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]'\n",
    "#\n",
    "# 给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。\n",
    "# \n",
    "# 规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。\n",
    "# \n",
    "# 请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。\n",
    "# \n",
    "# \n",
    "# \n",
    "# 提示：\n",
    "# \n",
    "# \n",
    "# 输出坐标的顺序不重要\n",
    "# m 和 n 都小于150\n",
    "# \n",
    "# \n",
    "# \n",
    "# \n",
    "# 示例：\n",
    "# \n",
    "# \n",
    "# \n",
    "# \n",
    "# 给定下面的 5x5 矩阵:\n",
    "# \n",
    "# ⁠ 太平洋 ~   ~   ~   ~   ~ \n",
    "# ⁠      ~  1   2   2   3  (5) *\n",
    "# ⁠      ~  3   2   3  (4) (4) *\n",
    "# ⁠      ~  2   4  (5)  3   1  *\n",
    "# ⁠      ~ (6) (7)  1   4   5  *\n",
    "# ⁠      ~ (5)  1   1   2   4  *\n",
    "# ⁠         *   *   *   *   * 大西洋\n",
    "# \n",
    "# 返回:\n",
    "# \n",
    "# [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).\n",
    "# \n",
    "# \n",
    "# \n",
    "# \n",
    "#\n",
    "from queue import Queue\n",
    "dx = [0, 0, 1, -1]\n",
    "dy = [1, -1, 0, 0]\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.cache = {1: {}, -1: {}}\n",
    "\n",
    "    def pacificAtlantic(self, matrix: 'List[List[int]]') -> 'List[List[int]]':\n",
    "        n = len(matrix)\n",
    "        if not n: return []\n",
    "        m = len(matrix[0])\n",
    "        for i in range(n):\n",
    "            self.bfs(matrix, i, m-1, -1)\n",
    "        for i in range(m):\n",
    "            self.bfs(matrix, n-1, i, -1)\n",
    "        for i in range(n):\n",
    "            self.bfs(matrix, i, 0, 1)\n",
    "        for i in range(m):\n",
    "            self.bfs(matrix, 0, i, 1)\n",
    "\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if self.cache[1].get((i, j), False) and self.cache[-1].get((i, j), False):\n",
    "                    ans.append([i, j])\n",
    "        return ans\n",
    "    \n",
    "    def bfs(self, matrix, x, y, flag):\n",
    "        self.cache[flag][(x, y)] = True\n",
    "        n = len(matrix)\n",
    "        m = len(matrix[0])\n",
    "        q = Queue()\n",
    "        q.put((x, y))\n",
    "\n",
    "        while not q.empty():\n",
    "            p = q.get()\n",
    "            self.cache[flag][p] = True\n",
    "            for i in range(4):\n",
    "                xx = p[0] + dx[i]\n",
    "                yy = p[1] + dy[i]\n",
    "                if 0<=xx<n and 0 <=yy<m and matrix[p[0]][p[1]] <= matrix[xx][yy] and (xx, yy) not in self.cache[flag]:\n",
    "                    self.cache[flag][(xx, yy)] = True\n",
    "                    q.put((xx, yy))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        answ=[]\n",
    "        if matrix==[]:\n",
    "            return answ\n",
    "        m=len(matrix[0])\n",
    "        n=len(matrix)\n",
    "        if m==1 and n==1:\n",
    "            answ.append([0,0])\n",
    "            return answ\n",
    "        visa=[[0 for col in range(m)] for row in range(n)]\n",
    "        visb=[[0 for col in range(m)] for row in range(n)]\n",
    "        def dfsa(x,y):\n",
    "            nonlocal matrix\n",
    "            nonlocal visa\n",
    "            visa[x][y]=1\n",
    "            if x:\n",
    "                if matrix[x-1][y]>=matrix[x][y] and not visa[x-1][y]:\n",
    "                    dfsa(x-1,y)\n",
    "            if y:\n",
    "                if matrix[x][y-1]>=matrix[x][y] and not visa[x][y-1]:\n",
    "                    dfsa(x,y-1)\n",
    "            if x<n-1:\n",
    "                if matrix[x+1][y]>=matrix[x][y] and not visa[x+1][y]:\n",
    "                    dfsa(x+1,y)\n",
    "            if y<m-1:\n",
    "                if matrix[x][y+1]>=matrix[x][y] and not visa[x][y+1]:\n",
    "                    dfsa(x,y+1)\n",
    "            return\n",
    "        def dfsb(x,y):\n",
    "            nonlocal matrix\n",
    "            nonlocal visb\n",
    "            visb[x][y]=1\n",
    "            if x:\n",
    "                if matrix[x-1][y]>=matrix[x][y] and not visb[x-1][y]:\n",
    "                    dfsb(x-1,y)\n",
    "            if y:\n",
    "                if matrix[x][y-1]>=matrix[x][y] and not visb[x][y-1]:\n",
    "                    dfsb(x,y-1)\n",
    "            if x<n-1:\n",
    "                if matrix[x+1][y]>=matrix[x][y] and not visb[x+1][y]:\n",
    "                    dfsb(x+1,y)\n",
    "            if y<m-1:\n",
    "                if matrix[x][y+1]>=matrix[x][y] and not visb[x][y+1]:\n",
    "                    dfsb(x,y+1)\n",
    "            return\n",
    "        for i in range(n):\n",
    "            if not visa[i][0]:\n",
    "                dfsa(i,0)\n",
    "            if not visb[i][m-1]:\n",
    "                dfsb(i,m-1)\n",
    "        for i in range(m):\n",
    "            if not visa[0][i]:\n",
    "                dfsa(0,i)\n",
    "            if not visb[n-1][i]:\n",
    "                dfsb(n-1,i)\n",
    "        for j in range(n):\n",
    "            for i in range(m):\n",
    "                if visa[j][i] and visb[j][i]:\n",
    "                    answ.append([j,i])\n",
    "        return answ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if not matrix or not matrix[0]:\n",
    "            return []\n",
    "\n",
    "        m, n = len(matrix), len(matrix[0])        \n",
    "        Pacific = [[0] * n for i in range(m)]\n",
    "        visited1 = [[0] * n for i in range(m)]\n",
    "        Atlantic = [[0] * n for i in range(m)]\n",
    "        visited2 = [[0] * n for i in range(m)]\n",
    "        directions = ((1, 0), (-1, 0), (0, 1), (0, -1))\n",
    "\n",
    "        def dfs(pos, isPacific):\n",
    "            i, j = pos\n",
    "            visited = visited1 if isPacific else visited2\n",
    "            if not visited[i][j]:\n",
    "                visited[i][j] = 1\n",
    "                for x, y in directions:\n",
    "                    ii, jj = i + x, j + y\n",
    "                    if 0 <= ii < m and 0 <= jj < n:\n",
    "                        if matrix[ii][jj] >= matrix[i][j]:\n",
    "                            dfs((ii, jj), isPacific)\n",
    "\n",
    "        for j in range(n):\n",
    "            dfs((0, j), 1)\n",
    "        for i in range(m):\n",
    "            dfs((i, 0), 1)\n",
    "\n",
    "        for j in range(n):\n",
    "            dfs((m-1, j), 0)\n",
    "        for i in range(m):\n",
    "            dfs((i, n-1), 0)\n",
    "\n",
    "        res = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if visited1[i][j] and visited2[i][j]:\n",
    "                    res.append([i, j])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if not matrix:\n",
    "            return []\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [ [] for i in range(m)] \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dp[i].append([False, False])\n",
    "\n",
    "        queue = [(i, j) for i in range(m) for j in range(n) if i == 0  or j == 0]\n",
    "        for x, y in queue:\n",
    "            if dp[x][y][0]:\n",
    "                continue\n",
    "            dp[x][y][0] = True\n",
    "            for dx, dy in [[0,1], [0,-1], [1, 0], [-1, 0]]:\n",
    "                new_x, new_y = x + dx, y + dy\n",
    "                if not (0 <= new_x <m and 0 < new_y < n):\n",
    "                    continue\n",
    "                if matrix[new_x][new_y] >= matrix[x][y]:\n",
    "                    queue.append((new_x, new_y))\n",
    "        \n",
    "        \n",
    "        queue = [(i, j) for i in range(m) for j in range(n) if i == m-1  or j == n-1]\n",
    "        for x, y in queue:\n",
    "            if dp[x][y][1]:\n",
    "                continue\n",
    "            #print(\"setting #1 True for [\", x, y, \"],\", matrix[x][y])\n",
    "            dp[x][y][1] = True\n",
    "        \n",
    "            for dx, dy in [[0,1], [0,-1], [1, 0], [-1, 0]]:\n",
    "                new_x, new_y = x + dx, y + dy\n",
    "                if not (0 <= new_x <m and 0 <= new_y < n):\n",
    "                    continue\n",
    "                if matrix[new_x][new_y] >= matrix[x][y]:\n",
    "                    queue.append((new_x, new_y))\n",
    "        \n",
    "        #for i in range(m):\n",
    "        #    print(dp[i])\n",
    "        \n",
    "        res = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if dp[i][j][0] and dp[i][j][1]:\n",
    "                    res.append([i,j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "\n",
    "  def pacificAtlantic(self, matrix):\n",
    "    \"\"\"\n",
    "    :type matrix: List[List[int]]\n",
    "    :rtype: List[List[int]]\n",
    "    \"\"\"\n",
    "    if not matrix:\n",
    "      return []\n",
    "    n, m = len(matrix), len(matrix[0])\n",
    "    pacific = {(0, i) for i in range(m)}|{(i, 0) for i in range(n)}\n",
    "    atlantic = {(n - 1, i) for i in range(m)} | {(i, m - 1) for i in range(n)}\n",
    "    ans = []\n",
    "\n",
    "    def dfs(matrix, visited, i, j):\n",
    "      # | 取并集\n",
    "      visited |= {(i, j)}\n",
    "      for di, dj in [(0, -1), (0, 1), (-1, 0), (1, 0)]:\n",
    "        ni, nj = i + di, j + dj\n",
    "        if 0 <= ni < n and 0 <= nj < m and (ni, nj) not in visited:\n",
    "          if matrix[ni][nj] >= matrix[i][j]:\n",
    "            dfs(matrix, visited, ni, nj)\n",
    "\n",
    "    for i in range(n):\n",
    "      dfs(matrix, pacific, i, 0)\n",
    "      dfs(matrix, atlantic, i, m - 1)\n",
    "    for j in range(m):\n",
    "      dfs(matrix, pacific, 0, j)\n",
    "      dfs(matrix, atlantic, n - 1, j)\n",
    "    #  &交集\n",
    "    return list(pacific & atlantic)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "\n",
    "        # 采用DFS+剪枝\n",
    "        if not matrix:\n",
    "            return []\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        # 将已经搜索过的格子建立成字典，达到剪枝的效果\n",
    "        # key表示格子坐标，(row_idx, col_idx)\n",
    "        # value是两个bit的整数，第0bit表示能否流向太平洋，第1bit表示能否流向大西洋\n",
    "        # bit为0表示不能流向，为1表示能够流入\n",
    "        flow_dict = dict()\n",
    "        result_list = []\n",
    "\n",
    "        # 接下来采用DFS进行搜索，从四条边开始往中间搜索\n",
    "        min_dim = min(m, n)\n",
    "        half_min_dim = min_dim // 2 + min_dim % 2\n",
    "        for layer_idx in range(half_min_dim):\n",
    "            # 处理两列\n",
    "            for row_idx in range(layer_idx, m-layer_idx):\n",
    "                # 左边的一列\n",
    "                search_matrix = [[0]*n for _ in range(m)]  # 每个网格搜索时候存储中间搜索状态的矩阵\n",
    "                flow_dict[(row_idx, layer_idx)] = self.dfs_search(matrix, row_idx, layer_idx, result_list, flow_dict,\n",
    "                                                                  m, n, search_matrix)\n",
    "                if flow_dict[(row_idx, layer_idx)] is 3:\n",
    "                    result_list.append([row_idx, layer_idx])\n",
    "\n",
    "                # 右边的一列\n",
    "                if (row_idx, n-layer_idx-1) not in flow_dict:\n",
    "                    search_matrix = [[0]*n for _ in range(m)]  # 每个网格搜索时候存储中间搜索状态的矩阵\n",
    "                    flow_dict[(row_idx, n-layer_idx-1)] = self.dfs_search(matrix, row_idx, n-layer_idx-1, result_list,\n",
    "                                                                          flow_dict, m, n, search_matrix)\n",
    "                    if flow_dict[(row_idx, n-layer_idx-1)] is 3:\n",
    "                        result_list.append([row_idx, n-layer_idx-1])\n",
    "\n",
    "            # 处理两行\n",
    "            for col_idx in range(layer_idx+1, n-layer_idx-1):\n",
    "                # 上边的一行\n",
    "                if (layer_idx, col_idx) not in flow_dict:\n",
    "                    search_matrix = [[0]*n for _ in range(m)]  # 每个网格搜索时候存储中间搜索状态的矩阵\n",
    "                    flow_dict[(layer_idx, col_idx)] = self.dfs_search(matrix, layer_idx, col_idx, result_list, flow_dict,\n",
    "                                                                      m, n, search_matrix)\n",
    "                    if flow_dict[(layer_idx, col_idx)] is 3:\n",
    "                        result_list.append([layer_idx, col_idx])\n",
    "\n",
    "                # 下边的一行\n",
    "                if (m-layer_idx-1, col_idx) not in flow_dict:\n",
    "                    search_matrix = [[0]*n for _ in range(m)]  # 每个网格搜索时候存储中间搜索状态的矩阵\n",
    "                    flow_dict[(m-layer_idx-1, col_idx)] = self.dfs_search(matrix, m-layer_idx-1, col_idx, result_list,\n",
    "                                                                          flow_dict, m, n, search_matrix)\n",
    "                    if flow_dict[(m-layer_idx-1, col_idx)] is 3:\n",
    "                        result_list.append([m-layer_idx-1, col_idx])\n",
    "\n",
    "        # for row_idx in range(m):\n",
    "        #     for col_idx in range(n):\n",
    "        #         search_matrix = [[0]*n for _ in range(m)]  # 每个网格搜索时候存储中间搜索状态的矩阵\n",
    "        #         flow_dict[(row_idx, col_idx)] = self.dfs_search(matrix, row_idx, col_idx, result_list, flow_dict, m, n,\n",
    "        #                                                         search_matrix)\n",
    "        #         if flow_dict[(row_idx, col_idx)] is 3:\n",
    "        #             result_list.append([row_idx, col_idx])\n",
    "\n",
    "        return result_list\n",
    "\n",
    "    def dfs_search(self, matrix, row_num, col_num, result_list, flow_dict, m, n, search_matrix):\n",
    "        if (row_num, col_num) in flow_dict:\n",
    "            # 直接返回已有结果\n",
    "            return flow_dict[(row_num, col_num)]\n",
    "        else:\n",
    "            # 查看上下左右有没有可以流动的方向\n",
    "            # 如果在搜索中碰到上下左右的search_matrix有为4的，就放弃这条路径\n",
    "\n",
    "            # 检查上边网格\n",
    "            if row_num is 0:\n",
    "                # 可以流入太平洋\n",
    "                search_matrix[row_num][col_num] |= 1\n",
    "            elif matrix[row_num][col_num] >= matrix[row_num-1][col_num]:\n",
    "                if search_matrix[row_num-1][col_num] is 4:\n",
    "                    # 放弃这个方向，因为搜索就是从这个方向过来的\n",
    "                    pass\n",
    "                else:\n",
    "                    store_val = search_matrix[row_num][col_num]\n",
    "                    search_matrix[row_num][col_num] = 4\n",
    "                    tmp_result = self.dfs_search(matrix, row_num-1, col_num, result_list, flow_dict, m, n, search_matrix)\n",
    "                    search_matrix[row_num][col_num] = store_val | tmp_result\n",
    "            else:\n",
    "                search_matrix[row_num][col_num] |= 0\n",
    "\n",
    "            if search_matrix[row_num][col_num] is 3:\n",
    "                return 3\n",
    "\n",
    "            # 检查下边网格\n",
    "            if row_num is m-1:\n",
    "                # 可以流入大西洋\n",
    "                search_matrix[row_num][col_num] |= 2\n",
    "            elif matrix[row_num][col_num] >= matrix[row_num+1][col_num]:\n",
    "                if search_matrix[row_num+1][col_num] is 4:\n",
    "                    # 放弃这个方向，因为搜索就是从这个方向过来的\n",
    "                    pass\n",
    "                else:\n",
    "                    store_val = search_matrix[row_num][col_num]\n",
    "                    search_matrix[row_num][col_num] = 4\n",
    "                    tmp_result = self.dfs_search(matrix, row_num+1, col_num, result_list, flow_dict, m, n, search_matrix)\n",
    "                    search_matrix[row_num][col_num] = store_val | tmp_result\n",
    "            else:\n",
    "                search_matrix[row_num][col_num] |= 0\n",
    "\n",
    "            if search_matrix[row_num][col_num] is 3:\n",
    "                return 3\n",
    "\n",
    "            # 检查左边网格\n",
    "            if col_num is 0:\n",
    "                # 可以流入太平洋\n",
    "                search_matrix[row_num][col_num] |= 1\n",
    "            elif matrix[row_num][col_num] >= matrix[row_num][col_num-1]:\n",
    "                if search_matrix[row_num][col_num-1] is 4:\n",
    "                    # 放弃这个方向，因为搜索就是从这个方向过来的\n",
    "                    pass\n",
    "                else:\n",
    "                    store_val = search_matrix[row_num][col_num]\n",
    "                    search_matrix[row_num][col_num] = 4\n",
    "                    tmp_result = self.dfs_search(matrix, row_num, col_num-1, result_list, flow_dict, m, n, search_matrix)\n",
    "                    search_matrix[row_num][col_num] = store_val | tmp_result\n",
    "            else:\n",
    "                search_matrix[row_num][col_num] |= 0\n",
    "\n",
    "            if search_matrix[row_num][col_num] is 3:\n",
    "                return 3\n",
    "\n",
    "            # 检查右边网格\n",
    "            if col_num is n-1:\n",
    "                # 可以流入大西洋\n",
    "                search_matrix[row_num][col_num] |= 2\n",
    "            elif matrix[row_num][col_num] >= matrix[row_num][col_num+1]:\n",
    "                if search_matrix[row_num][col_num+1] is 4:\n",
    "                    # 放弃这个方向，因为搜索就是从这个方向过来的\n",
    "                    pass\n",
    "                else:\n",
    "                    store_val = search_matrix[row_num][col_num]\n",
    "                    search_matrix[row_num][col_num] = 4\n",
    "                    tmp_result = self.dfs_search(matrix, row_num, col_num+1, result_list, flow_dict, m, n, search_matrix)\n",
    "                    search_matrix[row_num][col_num] = store_val | tmp_result\n",
    "            else:\n",
    "                search_matrix[row_num][col_num] |= 0\n",
    "\n",
    "            return search_matrix[row_num][col_num]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, matrix: 'List[List[int]]') -> 'List[List[int]]':\n",
    "        if not matrix:\n",
    "            return []\n",
    "        unvisited = [[True for column in range(len(matrix[0]))] for row in range(len(matrix))]\n",
    "        result = []\n",
    "        self.results = [[None for column in range(len(matrix[0]))] for row in range(len(matrix))]\n",
    "        for x in range(len(matrix)):\n",
    "            for y in range(len(matrix[0])):\n",
    "                if self.dfs(matrix, x, y, x, y,unvisited) == \"PA\":\n",
    "                    result.append([x, y])\n",
    "        return result\n",
    "\n",
    "    def dfs(self, matrix, x, y, a, b, unvisited):\n",
    "        if self.results[x][y] and (x < a or (x == a and y < b)):\n",
    "            return self.results[x][y]\n",
    "        result = \"N\"\n",
    "        if x == 0 or y == 0:\n",
    "            if x == len(matrix) - 1 or y == len(matrix[0]) - 1:\n",
    "                self.results[x][y] = \"PA\"\n",
    "                return \"PA\"\n",
    "            else:\n",
    "                result = \"P\"\n",
    "        elif x == len(matrix) - 1 or y == len(matrix[0]) - 1:\n",
    "            result = \"A\"\n",
    "        else:\n",
    "            result = \"N\"\n",
    "        unvisited[x][y] = False\n",
    "        directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]\n",
    "        for direction in directions:\n",
    "            x1, y1 = x + direction[0], y + direction[1]\n",
    "            if x1 >= 0 and x1 < len(matrix) and y1 >= 0 and y1 < len(matrix[0]) and matrix[x][y] >= matrix[x1][y1] and unvisited[x1][y1]:\n",
    "                r = self.dfs(matrix, x1, y1, a, b, unvisited)\n",
    "                if r == \"N\":\n",
    "                    pass\n",
    "                elif (r == \"P\" and result != \"A\") or (r == \"A\" and result != \"P\"):\n",
    "                    result = r\n",
    "                else:\n",
    "                    self.results[x][y] = \"PA\"\n",
    "                    unvisited[x][y] = True\n",
    "                    return \"PA\"\n",
    "        self.results[x][y] = result\n",
    "        unvisited[x][y] = True\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        if not matrix: return []\n",
    "        R = len(matrix)\n",
    "        C = len(matrix[0])\n",
    "\n",
    "        def neighbors(i, j):\n",
    "            for row, col in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:\n",
    "                if 0<=row<R and 0<=col<C:\n",
    "                    yield row, col\n",
    "\n",
    "        pac_list = [(0, i) for i in range(C)] + [(i, 0) for i in range(1, R)]\n",
    "        atl_list = [(R-1, i) for i in range(C)] + [(i, C-1) for i in range(R-1)]\n",
    "\n",
    "        pacific = [[False] * C for _ in range(R)]\n",
    "        atlantic = [[False] * C for _ in range(R)]\n",
    "\n",
    "        for el in pac_list:\n",
    "            queue = [el]\n",
    "            while queue:\n",
    "                cur = queue.pop(0)\n",
    "                pacific[cur[0]][cur[1]] = True\n",
    "                \n",
    "                for i, j in neighbors(cur[0], cur[1]):\n",
    "                    if not pacific[i][j] and matrix[i][j] >= matrix[cur[0]][cur[1]]:\n",
    "                        pacific[i][j] = True\n",
    "                        queue.append((i, j))\n",
    "                    # pacific[i][j] = True\n",
    "                    \n",
    "        \n",
    "        for el in atl_list:\n",
    "            queue = [el]\n",
    "            while queue:\n",
    "                cur = queue.pop(0)\n",
    "                atlantic[cur[0]][cur[1]] = True\n",
    "                \n",
    "                for i, j in neighbors(cur[0], cur[1]):\n",
    "                    if not atlantic[i][j] and matrix[i][j] >= matrix[cur[0]][cur[1]]:\n",
    "                        atlantic[i][j] = True\n",
    "                        queue.append((i, j))\n",
    "                    # atlantic[i][j] = True\n",
    "\n",
    "        \n",
    "        res = []\n",
    "        for i in range(R):\n",
    "            for j in range(C):\n",
    "                if pacific[i][j] and atlantic[i][j]:\n",
    "                    res.append((i, j))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        if not matrix or len(matrix)==0:\n",
    "            return []\n",
    "        row, col = len(matrix), len(matrix[0])\n",
    "        to = [(-1,0),(0,-1),(1,0),(0,1)]\n",
    "        # 构建分别可以到达两个位置的集合\n",
    "        tpy = set()\n",
    "        dxy = set()\n",
    "        def dfs(r ,c, res):\n",
    "            # 因为集合即使坐标存在也不会重复加入\n",
    "            res.add((r, c))\n",
    "            for i, j in to:\n",
    "                new_r = r + i\n",
    "                new_c = c + j\n",
    "                # 不越界 且 符合高到低或同等的高度流动原则\n",
    "                if 0<=new_r<row and 0<=new_c<col and matrix[r][c] <= matrix[new_r][new_c] and (new_r,new_c) not in res:\n",
    "                    dfs(new_r, new_c,res)\n",
    "        \n",
    "        # 从四个边界遍历如果比上一个小就以到达加入答案中\n",
    "        for c in range(col):\n",
    "            dfs(0, c ,tpy)\n",
    "            dfs(row-1, c, dxy)\n",
    "        for r in range(row):\n",
    "            dfs(r, 0, tpy)\n",
    "            dfs(r, col-1,dxy)\n",
    "        return [list(i) for i in tpy&dxy]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        if not matrix:\n",
    "            return []\n",
    "        \n",
    "        p_visited = set()\n",
    "        a_visited = set()\n",
    "\n",
    "        rows = len(matrix)\n",
    "        cols = len(matrix[0])\n",
    "        \n",
    "        self.directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "\n",
    "        for row in range(rows):\n",
    "            p_visited.add((row, 0))\n",
    "            a_visited.add((row, cols - 1))\n",
    "            \n",
    "        for col in range(cols):\n",
    "            p_visited.add((0, col))\n",
    "            a_visited.add((rows-1, col))\n",
    "            \n",
    "        self.bfs(matrix, p_visited, rows, cols)\n",
    "        self.bfs(matrix, a_visited, rows, cols)\n",
    "        \n",
    "        return list(p_visited.intersection(a_visited))\n",
    "    \n",
    "    def bfs(self, matrix, ocean, rows, cols):\n",
    "            q = collections.deque(ocean)\n",
    "            while q:\n",
    "                r, c = q.popleft()\n",
    "                for dirs in self.directions:\n",
    "                    next_r = r + dirs[0]\n",
    "                    next_c = c + dirs[1]\n",
    "                    \n",
    "                    if 0 <= next_r < rows and 0 <= next_c < cols:\n",
    "                        if (next_r, next_c) not in ocean:\n",
    "                            if matrix[next_r][next_c] >= matrix[r][c]:\n",
    "                                q.append((next_r, next_c))\n",
    "                                ocean.add((next_r, next_c))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return []\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        A = [[False]*n for i in range(m)]\n",
    "        B = [[False]*n for i in range(m)]\n",
    "\n",
    "        # 太平洋\n",
    "        pos = [([0, i], matrix[0][i]) for i in range(n)] + [([i,0], matrix[i][0]) for i in range(1,m)]\n",
    "        for p, _ in pos:\n",
    "            A[p[0]][p[1]]=True\n",
    "\n",
    "        while pos:\n",
    "            new_pos = []\n",
    "            for p, h in pos:\n",
    "                neigh = [[p[0]-1, p[1]], [p[0]+1, p[1]], [p[0], p[1]-1], [p[0], p[1]+1]]\n",
    "                for x, y in neigh:\n",
    "                    if 0<=x<m and 0<=y<n and matrix[x][y]>=h and not A[x][y]:\n",
    "                        A[x][y] = True\n",
    "                        new_pos.append(([x, y], matrix[x][y]))\n",
    "            pos = new_pos\n",
    "\n",
    "        # 大西洋\n",
    "        pos = [([m-1, i], matrix[m-1][i]) for i in range(n)] + [([i,n-1], matrix[i][n-1]) for i in range(m-1)]\n",
    "        for p, _ in pos:\n",
    "            B[p[0]][p[1]]=True\n",
    "\n",
    "        while pos:\n",
    "            new_pos = []\n",
    "            for p, h in pos:\n",
    "                neigh = [[p[0]-1, p[1]], [p[0]+1, p[1]], [p[0], p[1]-1], [p[0], p[1]+1]]\n",
    "                for x, y in neigh:\n",
    "                    if 0<=x<m and 0<=y<n and matrix[x][y]>=h and not B[x][y]:\n",
    "                        B[x][y] = True\n",
    "                        new_pos.append(([x, y], matrix[x][y]))\n",
    "            pos = new_pos\n",
    "\n",
    "        out = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if A[i][j] and B[i][j]:\n",
    "                    out.append([i,j])\n",
    "        return out\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from itertools import product\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        if not matrix:\n",
    "            return []\n",
    "        width, height = len(matrix[0]), len(matrix)\n",
    "        result = list()\n",
    "        # 1 表示通太平洋, 2表示通大西洋, 3表示两者都通\n",
    "        data = [[0] * width for i in range(height)]\n",
    "        queue = deque()\n",
    "\n",
    "        for i in range(width):\n",
    "            queue.append((i, 0))\n",
    "        for i in range(height):\n",
    "            queue.append((0, i))\n",
    "    \n",
    "        while queue:\n",
    "            current = queue.popleft()\n",
    "            x, y = current[0], current[1]\n",
    "            data[y][x] |= 1\n",
    "            for nei in ((x-1, y), (x+1,y), (x, y-1), (x, y+1)):\n",
    "                this_x, this_y = nei[0], nei[1]\n",
    "                if 0 <= this_x < width and 0 <= this_y < height and not (data[this_y][this_x] & 1) and matrix[this_y][this_x] >= matrix[y][x]:\n",
    "                    queue.append(nei)\n",
    "\n",
    "        for i in range(width):\n",
    "            queue.append((i, height-1))\n",
    "        for i in range(height):\n",
    "            queue.append((width-1,i))\n",
    "\n",
    "        while queue:\n",
    "            current = queue.popleft()\n",
    "            x, y = current[0], current[1]\n",
    "            data[y][x] |= 2\n",
    "            \n",
    "            for nei in ((x-1, y), (x+1,y), (x, y-1), (x, y+1)):\n",
    "                this_x, this_y = nei[0], nei[1]\n",
    "                if 0 <= this_x < width and 0 <= this_y < height and not (data[this_y][this_x] & 2) and matrix[this_y][this_x] >= matrix[y][x]:\n",
    "                    queue.append(nei)\n",
    "\n",
    "        for x, y in product(range(width),range(height)):\n",
    "            if data[y][x] == 3:\n",
    "                result.append([y, x])\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        if not matrix or not matrix[0]: return []\n",
    "        # 能流到太平洋的所有位置，从太平洋边界倒推\n",
    "        res1 = set()\n",
    "        # 能流到大西洋的所有位置，从大西洋洋边界倒推\n",
    "        res2 = set()\n",
    "\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "\n",
    "        # 从边界遍历\n",
    "        def dfs(i, j, res):\n",
    "            res.add((i, j))\n",
    "            for x, y in [[1, 0], [-1, 0], [0, 1], [0, -1]]:\n",
    "                tmp_i = i + x\n",
    "                tmp_j = j + y\n",
    "                if 0 <= tmp_i < row and 0 <= tmp_j < col and matrix[i][j] <= matrix[tmp_i][tmp_j] and (tmp_i, tmp_j) not in res:\n",
    "                    dfs(tmp_i, tmp_j, res)\n",
    "\n",
    "        # 太平洋\n",
    "        for i in range(row):\n",
    "            dfs(i, 0, res1)\n",
    "        # 太平洋\n",
    "        for j in range(col):\n",
    "            dfs(0, j, res1)\n",
    "        # 大西洋\n",
    "        for i in range(row):\n",
    "            dfs(i, col - 1, res2)\n",
    "        # 大西洋\n",
    "        for j in range(col):\n",
    "            dfs(row - 1, j, res2)\n",
    "\n",
    "        # 两个集合的交集\n",
    "        return res1 & res2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        if not matrix or not matrix[0]: return []\n",
    "        # 流向太平洋的位置\n",
    "        res1 = set()\n",
    "        # 流向大西洋的位置\n",
    "        res2 = set()\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "\n",
    "        # 从边界遍历\n",
    "        def dfs(i, j, res):\n",
    "            res.add((i, j))\n",
    "            for x, y in [[1, 0], [-1, 0], [0, 1], [0, -1]]:\n",
    "                tmp_i = i + x\n",
    "                tmp_j = j + y\n",
    "                if 0 <= tmp_i < row and 0 <= tmp_j < col \\\n",
    "                    and matrix[i][j] <= matrix[tmp_i][tmp_j] \\\n",
    "                    and (tmp_i, tmp_j) not in res: \n",
    "                    dfs(tmp_i, tmp_j, res)\n",
    "        # 太平洋\n",
    "        for i in range(row):\n",
    "            dfs(i, 0, res1)\n",
    "        # 太平洋\n",
    "        for j in range(col):\n",
    "            dfs(0, j, res1)\n",
    "        # 大西洋\n",
    "        for i in range(row):\n",
    "            dfs(i, col - 1, res2)\n",
    "        # 大西洋\n",
    "        for j in range(col):\n",
    "            dfs(row - 1, j, res2)\n",
    "\n",
    "        return res1 & res2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:        \n",
    "        def BFS(start):\n",
    "            queue = collections.deque()\n",
    "            queue.append(start)\n",
    "            visited = set()\n",
    "            visited.add(start)\n",
    "            daxi = 0 # 用于检测是否到达大西洋\n",
    "            taiping = 0  # 用于检测是否到达太平洋\n",
    "            while queue:\n",
    "                nx, ny = queue.popleft()\n",
    "                for x, y in [(nx + 1, ny), (nx, ny + 1), (nx-1, ny), (nx, ny - 1)]:\n",
    "                    if 0 <= x < len(heights) and 0 <= y < len(heights[0]) \\\n",
    "                        and heights[x][y] <= heights[nx][ny] and (x, y) not in visited:\n",
    "                        queue.append((x, y))\n",
    "                        visited.add((x, y))\n",
    "\n",
    "                if nx == 0 or ny == 0:\n",
    "                    taiping = 1\n",
    "                if nx == len(heights)-1 or ny == len(heights[0])-1:\n",
    "                    daxi = 1\n",
    "                if daxi == 1 and taiping == 1:\n",
    "                    return True\n",
    "            return False\n",
    "        #print(BFS((1,4)))\n",
    "        res = []\n",
    "        for i in range(len(heights)):\n",
    "            for j in range(len(heights[0])):\n",
    "                if BFS((i, j)) == True:\n",
    "                    res.append((i, j))\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        def taiping_BFS(start):\n",
    "            queue = collections.deque()\n",
    "            if start not in visited_taiping:\n",
    "                queue.append(start)\n",
    "                visited_taiping.add(start)\n",
    "            while queue:\n",
    "                nx, ny = queue.popleft()\n",
    "                for x, y in [(nx + 1, ny), (nx, ny + 1), (nx-1, ny), (nx, ny - 1)]:\n",
    "                    if 0 <= x < len(heights) and 0 <= y < len(heights[0]) \\\n",
    "                        and heights[x][y] >= heights[nx][ny] \\\n",
    "                            and (x, y) not in visited_taiping:\n",
    "                        queue.append((x, y))\n",
    "                        visited_taiping.add((x, y))\n",
    "        def daxi_BFS(start):\n",
    "            queue = collections.deque()\n",
    "            if start not in visited_daxi:\n",
    "                queue.append(start)\n",
    "                visited_daxi.add(start)\n",
    "            while queue:\n",
    "                nx, ny = queue.popleft()\n",
    "                for x, y in [(nx + 1, ny), (nx, ny + 1), (nx-1, ny), (nx, ny - 1)]:\n",
    "                    if 0 <= x < len(heights) and 0 <= y < len(heights[0]) \\\n",
    "                        and heights[x][y] >= heights[nx][ny] \\\n",
    "                            and (x, y) not in visited_daxi:\n",
    "                        queue.append((x, y))\n",
    "                        visited_daxi.add((x, y))\n",
    "        visited_taiping = set()  # 存放能流向太平洋的坐标\n",
    "        visited_daxi = set() # 存放能流向大西洋的坐标\n",
    "        for x in range(len(heights)):\n",
    "            taiping_BFS((x, 0))\n",
    "            daxi_BFS((x, len(heights[0])-1))\n",
    "        for y in range(len(heights[0])):\n",
    "            taiping_BFS((0, y))\n",
    "            daxi_BFS((len(heights)-1, y))\n",
    "        return list(visited_taiping & visited_daxi)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        m=len(heights)\n",
    "        n=len(heights[0])\n",
    "        ans=[]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                sign1=0\n",
    "                sign2=0\n",
    "                q=collections.deque([(i,j)])\n",
    "                tabu={(i,j)}\n",
    "                while q:\n",
    "                    x,y=q.popleft()\n",
    "                    for u,v in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:\n",
    "                        if u<0 or v<0:\n",
    "                            sign1=1\n",
    "                        elif u>=m or v>=n:\n",
    "                            sign2=1\n",
    "                        else:\n",
    "                            if heights[u][v]<=heights[x][y] and (u,v) not in tabu:\n",
    "                                q.append((u,v))\n",
    "                                tabu.add((u,v))\n",
    "                    if sign1==1 and sign2==1:\n",
    "                        break\n",
    "                if sign1==1 and sign2==1:\n",
    "                    ans.append([i,j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        def bfs(starts):\n",
    "            q = deque(starts)\n",
    "            visited = set(starts)\n",
    "            while q:\n",
    "                x, y = q.popleft()\n",
    "                for nx, ny in ((x, y + 1), (x, y - 1), (x - 1, y), (x + 1, y)):\n",
    "                    if 0 <= nx < m and 0 <= ny < n and heights[nx][ny] >= heights[x][y] and (nx, ny) not in visited:\n",
    "                        q.append((nx, ny))\n",
    "                        visited.add((nx, ny))\n",
    "            return visited\n",
    "\n",
    "        pacific = [(0, i) for i in range(n)] + [(i, 0) for i in range(1, m)]\n",
    "        atlantic = [(m - 1, i) for i in range(n)] + [(i, n - 1) for i in range(m - 1)]\n",
    "        return list(map(list, bfs(pacific) & bfs(atlantic)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque \n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        m,n = len(heights), len(heights[0])\n",
    "        dq_tpy = deque()\n",
    "        dq_dxy = deque()\n",
    "        seen_tpy = set()\n",
    "        seen_dxy = set()\n",
    "        # 初始化队列\n",
    "        for x in range(n):\n",
    "            dq_tpy.appendleft((x,0))\n",
    "            dq_dxy.appendleft((x,m-1))\n",
    "        for y in range(m):\n",
    "            dq_tpy.appendleft((0,y))\n",
    "            dq_dxy.appendleft((n-1,y))\n",
    "        \n",
    "        # bfs搜索能流到太平洋里的点集\n",
    "        while len(dq_tpy)!=0:\n",
    "            x,y = dq_tpy.pop()\n",
    "            seen_tpy.add((x,y))\n",
    "\n",
    "            for dx, dy in [(0,-1), (-1,0), (0,1), (1,0)]:\n",
    "                if not( 0<=x+dx<n  and  0<=y+dy<m ):\n",
    "                    continue\n",
    "                \n",
    "                if (x+dx, y+dy) in seen_tpy:\n",
    "                    continue\n",
    "                \n",
    "                if heights[y+dy][x+dx] >= heights[y][x]:\n",
    "                    dq_tpy.appendleft((x+dx, y+dy)) \n",
    "        \n",
    "\n",
    "        # bfs搜索能流到大西洋里的点集\n",
    "        while len(dq_dxy)!=0:\n",
    "            x,y = dq_dxy.pop()\n",
    "            seen_dxy.add((x,y))\n",
    "\n",
    "            for dx, dy in [(0,-1), (-1,0), (0,1), (1,0)]:\n",
    "                if not( 0<=x+dx<n  and  0<=y+dy<m ):\n",
    "                    continue\n",
    "                \n",
    "                if (x+dx, y+dy) in seen_dxy:\n",
    "                    continue\n",
    "                \n",
    "                if heights[y+dy][x+dx] >= heights[y][x]:\n",
    "                    dq_dxy.appendleft((x+dx, y+dy)) \n",
    "\n",
    "        \n",
    "        res = seen_dxy & seen_tpy\n",
    "        # print(seen_dxy,seen_tpy)\n",
    "\n",
    "        res_ls = []\n",
    "        for x,y in res:\n",
    "            res_ls.append([y,x])\n",
    "        return res_ls\n",
    "\n",
    "                \n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        res = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        drcs = [[1, 0], [-1, 0], [0, 1], [0, -1]]\n",
    "        def dfs(r, c, state):\n",
    "            if (res[r][c] & state) == 0:\n",
    "                res[r][c] |= state\n",
    "                for dr, dc in drcs:\n",
    "                    if -1 < r + dr < m and -1 < c + dc < n and heights[r + dr][c + dc] >= heights[r][c]:\n",
    "                        dfs(r + dr, c + dc, state)\n",
    "\n",
    "        for r in range(m):\n",
    "            dfs(r, 0, 1)\n",
    "            dfs(r, n - 1, 2)\n",
    "        for c in range(n):\n",
    "            dfs(0, c, 1)\n",
    "            dfs(m - 1, c, 2)\n",
    "        ans = []\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if res[r][c] == 3: ans.append([r, c])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        res = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        drcs = [[1, 0], [-1, 0], [0, 1], [0, -1]]\n",
    "        def dfs(r, c, state):\n",
    "            if (res[r][c] & state) == 0:\n",
    "                res[r][c] |= state\n",
    "                for dr, dc in drcs:\n",
    "                    if -1 < r + dr < m and -1 < c + dc < n and heights[r + dr][c + dc] >= heights[r][c]:\n",
    "                        dfs(r + dr, c + dc, state)\n",
    "\n",
    "        for r in range(m):\n",
    "            dfs(r, 0, 1)\n",
    "            dfs(r, n - 1, 2)\n",
    "        for c in range(n):\n",
    "            dfs(0, c, 1)\n",
    "            dfs(m - 1, c, 2)\n",
    "        ans = []\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if res[r][c] == 3: ans.append([r, c])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        pacific = {(i, 0) for i in range(m)} | {(0, i) for i in range(n)}\n",
    "        atlantic = {(i, n - 1) for i in range(m)} | {(m - 1, i) for i in range(n)}\n",
    "        for ocean in (pacific, atlantic):\n",
    "            stack = list(ocean)\n",
    "            while stack:\n",
    "                x, y = stack.pop()\n",
    "                for i, j in ((x+1,y), (x-1,y), (x,y+1), (x,y-1)):\n",
    "                    if (i, j) not in ocean and 0 <= i < m and 0 <= j < n and heights[i][j] >= heights[x][y]:\n",
    "                        stack.append((i, j))\n",
    "                        ocean.add((i, j))\n",
    "        return [list(x) for x in pacific & atlantic]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        # 从Pacific 和 Atlantic反着标识\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        pacific = [[False]*n for _ in range(m)]\n",
    "        atlantic = [[False]*n for _ in range(m)]\n",
    "        def bfs(startR, startC, visited):\n",
    "            # 往高处走\n",
    "            visited[startR][startC] = True\n",
    "            q = deque([[startR, startC]])\n",
    "            while q:\n",
    "                curR, curC = q.popleft()\n",
    "                for diffR, diffC in [[-1, 0], [0, -1], [1, 0], [0, 1]]:\n",
    "                    nextR, nextC = curR + diffR, curC + diffC\n",
    "                    if  0 <= nextR < m and 0 <= nextC < n and not visited[nextR][nextC] and heights[nextR][nextC] >= heights[curR][curC]:\n",
    "                        visited[nextR][nextC] = True\n",
    "                        q.append([nextR, nextC])\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if (r == 0 or c == 0) and not pacific[r][c]:\n",
    "                    bfs(r, c, pacific)\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if (r == m-1 or c == n-1) and not atlantic[r][c]:\n",
    "                    bfs(r, c, atlantic)\n",
    "        ans = []\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if pacific[r][c] and atlantic[r][c]:\n",
    "                    ans.append([r,c])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        ret = []\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        print(m, n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                h = heights[i][j]\n",
    "                flag1, flag2 = False, False\n",
    "                q = [(i, j)]\n",
    "                visited = {(i,j):1}\n",
    "                \n",
    "                while q:\n",
    "                    next_q = []\n",
    "                    for x, y in q:\n",
    "                        if x == 0 or y == 0:\n",
    "                            flag1 = True\n",
    "                        if x == m-1 or y == n-1:\n",
    "                            flag2 = True\n",
    "                        for xx, yy in [(x, y-1), (x, y+1), (x-1, y), (x+1, y)]:\n",
    "                            if xx < 0 or yy < 0 or xx >= m or yy >= n:\n",
    "                                continue\n",
    "                            if (xx, yy) in visited:\n",
    "                                continue\n",
    "                            if heights[xx][yy] <= heights[x][y]:\n",
    "                                visited[(xx, yy)] = 1\n",
    "                                next_q.append((xx, yy))\n",
    "                    q = next_q\n",
    "                if flag1 and flag2:\n",
    "                    ret.append([i, j])\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(heights), len(heights[0])\n",
    "\n",
    "        # 1.反向搜索: 从海岸线往山上跑\n",
    "        # def search(starts: List[Tuple[int, int]]) -> Set[Tuple[int, int]]:\n",
    "        #     visited = set()\n",
    "            \n",
    "        #     # 深度优先搜索: 递归\n",
    "        #     def dfs(x: int, y: int):\n",
    "        #         if (x, y) in visited:\n",
    "        #             return\n",
    "        #         visited.add((x, y))\n",
    "        #         for nx, ny in ((x, y + 1), (x, y - 1), (x - 1, y), (x + 1, y)):\n",
    "        #             if 0 <= nx < m and 0 <= ny < n and heights[nx][ny] >= heights[x][y]:\n",
    "        #                 dfs(nx, ny)\n",
    "            \n",
    "        #     for x, y in starts:\n",
    "        #         dfs(x, y)\n",
    "        #     return visited\n",
    "\n",
    "        # # 两个大洋的海岸线\n",
    "        # pacific = [(0, i) for i in range(n)] + [(i, 0) for i in range(1, m)]\n",
    "        # atlantic = [(m - 1, i) for i in range(n)] + [(i, n - 1) for i in range(m - 1)]\n",
    "        # # 将结果取与\n",
    "        # ans = list(map(list, search(pacific) & search(atlantic)))\n",
    "        # return ans\n",
    "\n",
    "        # 2.广度优先搜索: 借助队列\n",
    "        # def bfs(starts: List[Tuple[int, int]]) -> Set[Tuple[int, int]]:\n",
    "        #     q = deque(starts)\n",
    "        #     visited = set(starts)\n",
    "        #     while q:\n",
    "        #         x, y = q.popleft()\n",
    "        #         for nx, ny in ((x, y + 1), (x, y - 1), (x - 1, y), (x + 1, y)):\n",
    "        #             if 0 <= nx < m and 0 <= ny < n and heights[nx][ny] >= heights[x][y] and (nx, ny) not in visited:\n",
    "        #                 q.append((nx, ny))\n",
    "        #                 visited.add((nx, ny))\n",
    "        #     return visited\n",
    "        \n",
    "        # pacific = [(0, i) for i in range(n)] + [(i, 0) for i in range(1, m)]\n",
    "        # atlantic = [(m - 1, i) for i in range(n)] + [(i, n - 1) for i in range(m - 1)]\n",
    "        # ans = list(map(list, bfs(pacific) & bfs(atlantic)))\n",
    "        # return ans\n",
    "\n",
    "        row, col = len(heights), len(heights[0])\n",
    "\n",
    "        def search(starts: List[Tuple[int, int]]) -> Set[Tuple[int, int]]:\n",
    "            visited = set()\n",
    "\n",
    "            def dfs(x: int, y: int):\n",
    "                if (x, y) in visited:\n",
    "                    return\n",
    "                visited.add((x, y))\n",
    "                for tmpx, tmpy in ((x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)):\n",
    "                    if 0 <= tmpx < row and 0 <= tmpy < col and heights[tmpx][tmpy] >= heights[x][y]:\n",
    "                        dfs(tmpx, tmpy)\n",
    "            \n",
    "            for x, y in starts:\n",
    "                dfs(x, y)\n",
    "            return visited\n",
    "        \n",
    "        pacific = [(0, i) for i in range(0, col)] + [(i, 0) for i in range(row)]\n",
    "        atlantic = [(row - 1, i) for i in range(0, col)] + [(i, col - 1) for i in range(0, row)]\n",
    "        ans = [list(res) for res in search(pacific) & search(atlantic)]\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.position = [[-1, 0], [0, 1], [1, 0], [0, -1]]\t# 四个方向\n",
    "\n",
    "    # heights：题目给定的二维数组， row：当前位置的行号， col：当前位置的列号\n",
    "    # sign：记录是哪一条河，两条河中可以一个为 0，一个为 1\n",
    "    # visited：记录这个位置可以到哪条河\n",
    "    def dfs(self, heights: List[List[int]], row: int, col: int, sign: int, visited: List[List[List[int]]]):\n",
    "        for current in self.position:\n",
    "            curRow, curCol = row + current[0], col + current[1]\n",
    "            # 索引下标越界\n",
    "            if curRow < 0 or curRow >= len(heights) or curCol < 0 or curCol >= len(heights[0]): continue\n",
    "            # 不满足条件或者已经被访问过\n",
    "            if heights[curRow][curCol] < heights[row][col] or visited[curRow][curCol][sign]: continue\n",
    "            visited[curRow][curCol][sign] = True\n",
    "            self.dfs(heights, curRow, curCol, sign, visited)\n",
    "\n",
    "    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        rowSize, colSize = len(heights), len(heights[0])\n",
    "        # visited 记录 [row, col] 位置是否可以到某条河，可以为 true，反之为 false；\n",
    "        # 假设太平洋的标记为 1，大西洋为 0\n",
    "        # ans 用来保存满足条件的答案\n",
    "        ans, visited = [], [[[False for _ in range(2)] for _ in range(colSize)] for _ in range(rowSize)]\n",
    "        for row in range(rowSize):\n",
    "            visited[row][0][1] = True\n",
    "            visited[row][colSize - 1][0] = True\n",
    "            self.dfs(heights, row, 0, 1, visited)\n",
    "            self.dfs(heights, row, colSize - 1, 0, visited)\n",
    "        for col in range(0, colSize):\n",
    "            visited[0][col][1] = True\n",
    "            visited[rowSize - 1][col][0] = True\n",
    "            self.dfs(heights, 0, col, 1, visited)\n",
    "            self.dfs(heights, rowSize - 1, col, 0, visited)\n",
    "        for row in range(rowSize):\n",
    "            for col in range(colSize):\n",
    "                # 如果该位置即可以到太平洋又可以到大西洋，就放入答案数组\n",
    "                if visited[row][col][0] and visited[row][col][1]:\n",
    "                    ans.append([row, col])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(heights)\n",
    "        n = len(heights[0])\n",
    "        to_pacific = [[0]*n for _ in range(m)]\n",
    "        to_pacific[0] = [1]*n\n",
    "        for i in range(m):\n",
    "            to_pacific[i][0] = 1\n",
    "        to_alantic = [[0]*n for _ in range(m)]\n",
    "        to_alantic[-1] = [1]*n\n",
    "        for i in range(m):\n",
    "            to_alantic[i][-1] = 1\n",
    "\n",
    "        # dp = [[False]*n for _ in range(m)]\n",
    "        # dp[0] = [True]*n\n",
    "        # for i in range(m):\n",
    "        #     dp[i][0] = True\n",
    "        # dp[-1] = [True]*n\n",
    "        # for i in range(m):\n",
    "        #     dp[i][-1] = True\n",
    "    \n",
    "        def dfs(i,j):\n",
    "            #走到大的就从下面return,走到走过的return当前值\n",
    "            if dp[i][j]:#说明走到了走过的了\n",
    "                if i == 0 or j == 0:\n",
    "                    to_pacific[i][j] = 1\n",
    "                if i == m-1 or j == n-1:\n",
    "                    to_alantic[i][j] = 1 \n",
    "                return to_pacific[i][j], to_alantic[i][j]\n",
    "            dp[i][j] = True\n",
    "\n",
    "            # if i == 0 or j == 0:\n",
    "            #     to_pacific[i][j] = 1\n",
    "            # if i == m-1 or j == n-1:\n",
    "            #     to_alantic[i][j] = 1\n",
    "\n",
    "            #看上边\n",
    "            if i > 0:\n",
    "                if heights[i][j] >= heights[i-1][j]:\n",
    "                    tmp1, tmp2 = dfs(i-1,j)\n",
    "                    to_pacific[i][j] = max(tmp1, to_pacific[i][j])\n",
    "                    to_alantic[i][j] = max(tmp2, to_alantic[i][j])\n",
    "            #看下边\n",
    "            if i < m-1:\n",
    "                if heights[i][j] >= heights[i+1][j]:\n",
    "                    tmp1, tmp2 = dfs(i+1,j)\n",
    "                    to_pacific[i][j] = max(tmp1, to_pacific[i][j])\n",
    "                    to_alantic[i][j] = max(tmp2, to_alantic[i][j])\n",
    "            #看左边\n",
    "            if j > 0:\n",
    "                if heights[i][j] >= heights[i][j-1]:\n",
    "                    tmp1, tmp2 = dfs(i,j-1)\n",
    "                    to_pacific[i][j] = max(tmp1, to_pacific[i][j])\n",
    "                    to_alantic[i][j] = max(tmp2, to_alantic[i][j])\n",
    "            #看右边\n",
    "            if j < n-1:\n",
    "                if heights[i][j] >= heights[i][j+1]:\n",
    "                    tmp1, tmp2 = dfs(i,j+1)\n",
    "                    to_pacific[i][j] = max(tmp1, to_pacific[i][j])\n",
    "                    to_alantic[i][j] = max(tmp2, to_alantic[i][j])\n",
    "            \n",
    "            return to_pacific[i][j], to_alantic[i][j]\n",
    "\n",
    "        # dfs_p(4,4)\n",
    "        # print(dp_p)\n",
    "        # print(to_pacific)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # if not dp[i][j]:#只考察没到过的\n",
    "                    #考察去pacific的是往左和上走\n",
    "                dp = [[False]*n for _ in range(m)]\n",
    "                to_pacific[i][j],to_alantic[i][j] = dfs(i,j)\n",
    "\n",
    "        # print(to_pacific)\n",
    "        # print(to_alantic)\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if to_pacific[i][j] and to_alantic[i][j]:\n",
    "                    ans.append([i,j])\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(heights)\n",
    "        n = len(heights[0])\n",
    "        to_pacific = [[0]*n for _ in range(m)]\n",
    "        to_pacific[0] = [1]*n\n",
    "        for i in range(m):\n",
    "            to_pacific[i][0] = 1\n",
    "        to_alantic = [[0]*n for _ in range(m)]\n",
    "        to_alantic[-1] = [1]*n\n",
    "        for i in range(m):\n",
    "            to_alantic[i][-1] = 1\n",
    "\n",
    "        # dp = [[False]*n for _ in range(m)]\n",
    "        # dp[0] = [True]*n\n",
    "        # for i in range(m):\n",
    "        #     dp[i][0] = True\n",
    "        # dp[-1] = [True]*n\n",
    "        # for i in range(m):\n",
    "        #     dp[i][-1] = True\n",
    "    \n",
    "        def dfs(i,j):\n",
    "            #走到大的就从下面return,走到走过的return当前值\n",
    "            if dp[i][j]:#说明走到了走过的了\n",
    "                if i == 0 or j == 0:\n",
    "                    to_pacific[i][j] = 1\n",
    "                if i == m-1 or j == n-1:\n",
    "                    to_alantic[i][j] = 1 \n",
    "                return to_pacific[i][j], to_alantic[i][j]\n",
    "            dp[i][j] = True\n",
    "\n",
    "            # if i == 0 or j == 0:\n",
    "            #     to_pacific[i][j] = 1\n",
    "            # if i == m-1 or j == n-1:\n",
    "            #     to_alantic[i][j] = 1\n",
    "\n",
    "            #看上边\n",
    "            if i > 0:\n",
    "                if heights[i][j] >= heights[i-1][j]:\n",
    "                    tmp1, tmp2 = dfs(i-1,j)\n",
    "                    to_pacific[i][j] = max(tmp1, to_pacific[i][j])\n",
    "                    to_alantic[i][j] = max(tmp2, to_alantic[i][j])\n",
    "            #看下边\n",
    "            if i < m-1:\n",
    "                if heights[i][j] >= heights[i+1][j]:\n",
    "                    tmp1, tmp2 = dfs(i+1,j)\n",
    "                    to_pacific[i][j] = max(tmp1, to_pacific[i][j])\n",
    "                    to_alantic[i][j] = max(tmp2, to_alantic[i][j])\n",
    "            #看左边\n",
    "            if j > 0:\n",
    "                if heights[i][j] >= heights[i][j-1]:\n",
    "                    tmp1, tmp2 = dfs(i,j-1)\n",
    "                    to_pacific[i][j] = max(tmp1, to_pacific[i][j])\n",
    "                    to_alantic[i][j] = max(tmp2, to_alantic[i][j])\n",
    "            #看右边\n",
    "            if j < n-1:\n",
    "                if heights[i][j] >= heights[i][j+1]:\n",
    "                    tmp1, tmp2 = dfs(i,j+1)\n",
    "                    to_pacific[i][j] = max(tmp1, to_pacific[i][j])\n",
    "                    to_alantic[i][j] = max(tmp2, to_alantic[i][j])\n",
    "            \n",
    "            return to_pacific[i][j], to_alantic[i][j]\n",
    "\n",
    "        # dfs_p(4,4)\n",
    "        # print(dp_p)\n",
    "        # print(to_pacific)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # if not dp[i][j]:#只考察没到过的\n",
    "                    #考察去pacific的是往左和上走\n",
    "                dp = [[False]*n for _ in range(m)]\n",
    "                to_pacific[i][j],to_alantic[i][j] = dfs(i,j)\n",
    "\n",
    "        print(to_pacific)\n",
    "        print(to_alantic)\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if to_pacific[i][j] and to_alantic[i][j]:\n",
    "                    ans.append([i,j])\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def __init__(self):\r\n",
    "        self.directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]\r\n",
    "    \r\n",
    "    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\r\n",
    "        m = len(heights)\r\n",
    "        n = len(heights[0])\r\n",
    "\r\n",
    "        # visited记录[row, col]位置的雨水是否可以流入某个海洋，假设大西洋的索引为0，太平洋的索引为1\r\n",
    "        visited = [[[False for _ in range(2)] for _ in range(n)] for _ in range(m)]\r\n",
    "        \r\n",
    "        result = []\r\n",
    "\r\n",
    "        queue = deque()\r\n",
    "\r\n",
    "        for i in range(m):\r\n",
    "            # 大西洋\r\n",
    "            visited[i][n - 1][0] = True\r\n",
    "            queue.append([i, n - 1, 0])\r\n",
    "\r\n",
    "            # 太平洋\r\n",
    "            visited[i][0][1] = True\r\n",
    "            queue.append([i, 0, 1])\r\n",
    "        \r\n",
    "        for j in range(0, n):\r\n",
    "            # 大西洋\r\n",
    "            visited[m - 1][j][0] = True\r\n",
    "            queue.append([m - 1, j, 0])\r\n",
    "\r\n",
    "            # 太平洋\r\n",
    "            visited[0][j][1] = True\r\n",
    "            queue.append([0, j, 1])\r\n",
    "        \r\n",
    "        self.bfs(heights, queue, visited)\r\n",
    "\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                if visited[i][j][0] and visited[i][j][1]:\r\n",
    "                    result.append([i, j])\r\n",
    "        \r\n",
    "        return result\r\n",
    "\r\n",
    "    def bfs(self, heights, queue, visited):\r\n",
    "        while queue:\r\n",
    "            x, y, ocean = queue.popleft()\r\n",
    "            for k in range(4):\r\n",
    "                next_i = x + self.directions[k][0]\r\n",
    "                next_j = y + self.directions[k][1]\r\n",
    "\r\n",
    "                if next_i < 0 or next_i >= len(heights):\r\n",
    "                    continue\r\n",
    "                if next_j < 0 or next_j >= len(heights[0]):\r\n",
    "                    continue\r\n",
    "                if visited[next_i][next_j][ocean]:\r\n",
    "                    continue\r\n",
    "                if heights[next_i][next_j] < heights[x][y]:\r\n",
    "                    continue\r\n",
    "                \r\n",
    "                queue.append([next_i, next_j, ocean])\r\n",
    "                visited[next_i][next_j][ocean] = True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        m,n=len(heights),len(heights[0])\n",
    "        pos=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "\n",
    "        def dfs(x,y,arr):\n",
    "            arr[x][y]=1\n",
    "            for dx,dy in pos:\n",
    "                xx,yy=x+dx,y+dy\n",
    "                if 0<=xx<m and 0<=yy<n and heights[xx][yy]>=heights[x][y] and not arr[xx][yy]:\n",
    "                    dfs(xx,yy,arr)\n",
    "\n",
    "        Pacific=[[0]*n for _ in range(m)]\n",
    "        Atlantic=[[0]*n for _ in range(m)]\n",
    "\n",
    "        for i in range(n):\n",
    "            dfs(0,i,Pacific)\n",
    "            dfs(m-1,i,Atlantic)\n",
    "        for j in range(m):\n",
    "            dfs(j,0,Pacific)\n",
    "            dfs(j,n-1,Atlantic)\n",
    "\n",
    "        return [[i,j] for i in range(m) for j in range(n) if Pacific[i][j] and Atlantic[i][j]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        def isValid(x, y):\n",
    "            if 0 <= x < m and 0 <= y < n:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        \n",
    "        def dfs(a, b, can):\n",
    "            if can[a][b]:\n",
    "                return\n",
    "            can[a][b] = True\n",
    "            for ele in dire:\n",
    "                x = a + ele[0]\n",
    "                y = b + ele[1]\n",
    "                if isValid(x, y) and heights[x][y] >= heights[a][b]:\n",
    "                    dfs(x, y, can)\n",
    "\n",
    "\n",
    "        dire = [[0,1], [0,-1], [-1,0], [1,0]]\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        res = []\n",
    "        canP = [[False for _ in range(n)] for _ in range(m)]\n",
    "        canA = [[False for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            dfs(i, 0, canP)\n",
    "            dfs(i, n-1, canA)\n",
    "        for j in range(n):\n",
    "            dfs(0, j, canP)\n",
    "            dfs(m-1, j, canA)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if canA[i][j] and canP[i][j]:\n",
    "                    res.append([i, j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        m,n=len(heights),len(heights[0])\n",
    "        pos=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "\n",
    "        def dfs(x,y,arr):\n",
    "            arr[x][y]=1\n",
    "            for dx,dy in pos:\n",
    "                xx,yy=x+dx,y+dy\n",
    "                if 0<=xx<m and 0<=yy<n and heights[xx][yy]>=heights[x][y] and not arr[xx][yy]:\n",
    "                    dfs(xx,yy,arr)\n",
    "\n",
    "        Pacific=[[0]*n for _ in range(m)]\n",
    "        Atlantic=[[0]*n for _ in range(m)]\n",
    "\n",
    "        for i in range(n):\n",
    "            dfs(0,i,Pacific)\n",
    "            dfs(m-1,i,Atlantic)\n",
    "        for j in range(m):\n",
    "            dfs(j,0,Pacific)\n",
    "            dfs(j,n-1,Atlantic)\n",
    "\n",
    "        return [[i,j] for i in range(m) for j in range(n) if Pacific[i][j] and Atlantic[i][j]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        result = []\n",
    "        direction = [(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        \n",
    "        count = [[0] * len(heights[0]) for _ in range(len(heights))]\n",
    "\n",
    "        def dfs(x,y):\n",
    "\n",
    "            if x < 0 or x >= len(heights) or y < 0 or y >= len(heights[0]) or visited[x][y]:\n",
    "                return\n",
    "\n",
    "            visited[x][y] = True\n",
    "            count[x][y] += 1\n",
    "            if count[x][y] == 2:\n",
    "                result.append([x,y])\n",
    "\n",
    "            for i in range(4):\n",
    "                new_x = x + direction[i][0]\n",
    "                new_y = y + direction[i][1]\n",
    "\n",
    "                if new_x < 0 or new_x >= len(heights) or new_y < 0 or new_y >= len(heights[0]):\n",
    "                    continue\n",
    "\n",
    "                if heights[new_x][new_y] < heights[x][y]:\n",
    "                    continue\n",
    "\n",
    "                dfs(new_x,new_y)\n",
    "\n",
    "        visited = [[False] * len(heights[0]) for _ in range(len(heights))]\n",
    "        for i in range(len(heights)):\n",
    "            if not visited[i][0]:\n",
    "                dfs(i,0)\n",
    "        for i in range(len(heights[0])):\n",
    "            if not visited[0][i]:\n",
    "                dfs(0,i)\n",
    "        \n",
    "        visited = [[False] * len(heights[0]) for _ in range(len(heights))]\n",
    "        for i in range(len(heights)):\n",
    "            if not visited[i][-1]:\n",
    "                dfs(i,len(heights[0])-1)\n",
    "        for i in range(len(heights[0])):\n",
    "            if not visited[-1][i]:\n",
    "                dfs(len(heights)-1,i)\n",
    "\n",
    "        return result\n",
    "        \n",
    "                \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(heights), len(heights[0])\n",
    "        # 如果直接以每个单元格作为起点模拟雨水的流动，则会重复遍历每个单元格，导致时间复杂度过高。\n",
    "        # 为了降低时间复杂度，可以从矩阵的边界开始反向搜索寻找雨水流向边界的单元格，反向搜索时，每次只能移动到高度相同或更大的单元格。这是因为低的可以流向某个海洋，高的一定也能流向这个海洋。\n",
    "        def dfs(x: int, y: int, vis: List[List[bool]]):\n",
    "            if vis[x][y]:\n",
    "                return\n",
    "            vis[x][y] = True\n",
    "            for nx, ny in ((x, y + 1), (x, y - 1), (x - 1, y), (x + 1, y)):\n",
    "                if 0 <= nx < m and 0 <= ny < n and heights[nx][ny] >= heights[x][y]:\n",
    "                    dfs(nx, ny, vis)\n",
    "        pac = [[False] * n for _ in range(m)]\n",
    "        atl = [[False] * n for _ in range(m)]\n",
    "        for i in range(n):\n",
    "            dfs(0, i, pac)\n",
    "            dfs(m-1, i, atl)\n",
    "        for i in range(m):\n",
    "            dfs(i, 0, pac)\n",
    "            dfs(i, n-1, atl)\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if pac[i][j] and atl[i][j]:\n",
    "                    ans.append([i, j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        m,n = len(heights),len(heights[0])\n",
    "\n",
    "        def search(starts):\n",
    "            visited = set()\n",
    "            def dfs(x,y):\n",
    "                if (x,y) in visited:\n",
    "                    return\n",
    "                visited.add((x,y))\n",
    "                for nx, ny in ((x, y + 1), (x, y - 1), (x - 1, y), (x + 1, y)):\n",
    "                    if 0 <= nx < m and 0 <= ny < n and heights[nx][ny] >= heights[x][y]:\n",
    "                        dfs(nx, ny)\n",
    "\n",
    "            for x,y in starts:\n",
    "                dfs(x,y)\n",
    "            return visited\n",
    "\n",
    "        pacific = [(0, i) for i in range(n)] + [(i, 0) for i in range(1, m)]\n",
    "        atlantic = [(m - 1, i) for i in range(n)] + [(i, n - 1) for i in range(m - 1)]\n",
    "        return list(map(list,search(pacific) & search(atlantic)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(heights), len(heights[0])\n",
    "\n",
    "        def search(starts: List[Tuple[int, int]]) -> Set[Tuple[int, int]]:\n",
    "            visited = set()\n",
    "            def dfs(x: int, y: int):\n",
    "                if (x, y) in visited:\n",
    "                    return\n",
    "                visited.add((x, y))\n",
    "                for nx, ny in ((x, y + 1), (x, y - 1), (x - 1, y), (x + 1, y)):\n",
    "                    if 0 <= nx < m and 0 <= ny < n and heights[nx][ny] >= heights[x][y]:\n",
    "                        dfs(nx, ny)\n",
    "            for x, y in starts:\n",
    "                dfs(x, y)\n",
    "            return visited\n",
    "        \n",
    "        pacific = [(0, i) for i in range(n)] + [(i, 0) for i in range(1, m)]\n",
    "        atlantic = [(m - 1, i) for i in range(n)] + [(i, n - 1) for i in range(m - 1)]\n",
    "        return list(map(list, search(pacific) & search(atlantic)))\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
